//
//  1143. 最长公共子序列.swift
//  Top600
//
//  Created by rjb on 2021/7/29.
//

import Foundation
class Solution1143 {
    // 最长公共子序列
    // 先求子问题
    // dp[i][j] 以i,j 结尾的最长公共子序列
    // 动态规划的问题，主要是定义dp，定义状态转移方程
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: text2.count + 1), count: text1.count + 1)
        let text1Array: [Character] = Array(text1)
        let text2Array: [Character] = Array(text2)
        for i in 1..<dp.count {
            for j in 1..<dp[0].count {
                if text1Array[i - 1] == text2Array[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }
        return dp[text1.count][text2.count]
    }
    static func test() {
        let solution = Solution1143()
        let text1 = "abcde"
        let text2 = "ace"
        let result = solution.longestCommonSubsequence(text1, text2)
        print(result)
    }
}
